/* eslint-disable no-param-reassign */
export function insertSort(A: number[]): number[] {
	for (let j = 1; j < A.length; j += 1) {
		const key = A[j]
		// Insert A[j] into the sorted sequence A[0 .. j - 1]
		let i = j - 1
		while (i >= 0 && A[i] > key) {
			A[i + 1] = A[i]
			i -= 1
		}
		A[i + 1] = key
	}

	return A
}

// console.log(sort([3, 2, 1]))
